/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/word-break-ii
   @Language: C++
   @Datetime: 19-06-19 09:54
   */


// Method 1 Backtracking, Time O(n^2), Space O(n), Time 251ms
class Solution {
	void backtrack(string &s, int pos, unordered_set<string> &dict, string &t, vector<string> &vs){
		if(pos>=s.length()){
			t.pop_back();
			vs.push_back(t);
			return;
		}
		for(int len=1; pos+len<=s.length(); ++len){
			string str=s.substr(pos,len);
			if(dict.count(str)){
				str=t+str+" ";
				backtrack(s,pos+len,dict,str,vs);
			}
		}
	}
public:
	/*
	 * @param s: A string
	 * @param wordDict: A set of words.
	 * @return: All possible sentences.
	 */
	vector<string> wordBreak(string &s, unordered_set<string> &wordDict) {
		// write your code here
		string t;
		vector<string> vs;
		unordered_set<char> dict;
		for(const auto &w:wordDict)
			for(const auto &c:w)
				dict.insert(c);
		for(const auto &c:s)
			if(dict.count(c)==0) return vs;
		backtrack(s,0,wordDict,t,vs);
		return vs;
	}
};
